package code;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;


public class BT107 {
	
	
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
    	List<List<Integer>> result=new ArrayList<List<Integer>>();
    	if(root==null)
    		return result;
    	Queue<TreeNode> queue=new LinkedList<TreeNode>();
    	Map<TreeNode,Integer> map=new HashMap<TreeNode,Integer>();
    	
    	queue.add(root);
    	map.put(root, 1);
    	int step=0;
    	List<Integer> list = null;
    	while(!queue.isEmpty()){
    		TreeNode head=queue.poll();
//    		System.out.println(head.val);
    		int dis=map.get(head);
    		if(step<dis){
    			step++;
    			if(list!=null)
    				result.add(0,list);
    			list=new ArrayList<Integer>();
    		}
    		list.add(head.val);
    		if(head.left!=null){
    			queue.add(head.left);
    			map.put(head.left, dis+1);
    		}
    		if(head.right!=null){
    			queue.add(head.right);
    			map.put(head.right, dis+1);
    		}
    	}
    	result.add(0,list);
//    	for(int i=0;i<result.size();i++){
//    		for(int j=0;j<result.get(i).size();j++)
//    			System.out.print(result.get(i).get(j)+" ");
//    		System.out.println();
//    	}
    	return result;
    }
    public static void main(String[] args){
//    	BT107 bt=new BT107();
//    	TreeNode root=new TreeNode(3);
//    	TreeNode a=new TreeNode(9);
//    	TreeNode b=new TreeNode(20);
//    	TreeNode c=new TreeNode(15);
//    	TreeNode d=new TreeNode(7);
//    	root.left=a;
//    	root.right=b;
//    	b.left=c;
//    	b.right=d;
//    	
//    	bt.levelOrderBottom(root);
    	int i=0;
    	do{
    		System.out.println(i);
    		i++;
    	}while(i<10);
    }
}
